virtual dom

一、什么是virtual dom

用js对象结构表示DOM树结构，然后用这个树构建一个真正的DOM树，插到文档中，当状态变更时，重新构造一颗新的对象树，然后将新的树和旧的树进行比较，记录差异，并把差异以打补丁的方式应用到真正的DOM树上来更新视图。本质是JS和DOM之间做了一个缓存。

用Javascript对象表示元素，对象中有三个属性：

二、virtual dom中的diff算法

核心：逐层比较→前端中很少跨层移动dom元素→时间复杂度O(n)

多个组件拥有同一个父组件，归为一个组，整组与变化后的情况做对比，缺了就补上，多了就删除（如果发现某一个节点发生变化，则不再遍历其子节点，直接统一删除整个节点及其子节点，把新节点直接替换上去）
算法
1. DFS记录差异
  
  对新旧两棵树进行深度优先遍历，这样每个节点就会有一个唯一的标记；每遍历到一个节点就把该节点和新的树进行对比，如果有差异的话就记录到一个对象里面。
2. 差异类型
  - 替换原来的结点：新旧节点tagName是否相同，不一样则需要替换
  - 移动、删除、新增子节点：列表对比算法
  - 修改节点属性/文本节点文本内容的改变：patch记录变化
3. 对于子节点重排变化（移动）：列表对比算法
  
  给子节点加上唯一标识key（tagName可能重复，不能用其进行对比），形成一个子节点列表。
  问题转化为已知新旧节点的顺序，求最小的插入、删除操作（Levenshtein Distance最小编辑距离）

三、Levenshtein Distance最小编辑距离

描述：编辑距离是指两个字串之间，由一个转成另一个所需的编辑操作次数。最小编辑距离，是指所需最小的编辑操作次数。
最小编辑距离通常作为一种相似度计算函数被用于多种实际应用中。

思路：动态规划，使用dp[][]二维数组记录每次计算的值。

编辑操作包括插入、删除和替换三种操作

举个例子：

假设str1=ABCD; str2=ACD
建立 $dp[str1.length+1][str2.length+1]$ ，#表示串前可以插入任何字符
初始化矩阵
遍历矩阵并计算 $dp[i][j]=\begin{cases} dp[i][j-1]+1 \quad\quad\quad\quad\quad(1)\\ dp[i-1][j]+1 \quad\quad\quad\quad\quad(2)\\ dp[i-1][j-1]+1:0 \quad\quad(3)\end{cases}$ （1）算法思想转化为：去掉str2末尾一个字符，变成str1的最小编辑距离+1

（2）算法思想转化为：去掉str1末尾一个字符，变成str2的最小编辑距离+1

（3）算法思想转化为：去掉str1和str2末尾各一个字符，若两个末尾字符相同+0，不同+1
str1和str2的最小编辑距离为 $dp[str1.length][str2.length]$

results matching ""